1. Field of the Invention
This invention relates to two-dimensional finite impulse response filter arrangements for filtering a signal that represents an image and comprises a sequence of digital words.
2. Description of the Prior Art
It is known to digitize a signal obtained by scanning a two-dimensional image or picture, for example a television signal, by sampling the signal at a sampling frequency fs, that is at predetermined intervals or clock periods T (where T=1/fs), to provide a digital image signal that comprises a sequence of digital words or samples (for example 8-bit words or samples) spaced in time by the interval T. Such an image signal can conveniently be manipulated. It can, for example, be reduced in size (compressed) in either or both dimensions, namely horizontally (that is in the direction in which the image is scanned in a line-sequential manner) or vertically (transverse to the image scanning direction), for instance in the creation of digital video effects. As will now be described, in the absence of a suitable corrective measure compression of the image can give rise to aliasing.
As is known to those skilled in the art, an image can be characterized by a two-dimensional parameter known as spatial frequency, which is proportional to the reciprocal of the angle subtended to the eye of the viewer by the visual spectral components of the image. The concept of spatial frequency can more readily be appreciated by considering an image in the form of a series of uniformly spaced straight lines. For a fixed position of the viewer with respect to such an image, the image has a single spatial frequency which is inversely proportional to the apparent spacing of the lines. (The spatial frequency is horizontal if the lines are spaced horizontally, vertical if the lines are spaced vertically, and diagonal in other cases). Clearly, if the image is compressed, so that the lines appear to the viewer to become closer together whereby the angle they subtend to the eye of the viewer decreases, the spatial frequency increases.
The scaling theorem in Fourier analysis states that if an image signal is compressed in the spatial domain, that is if the spatial frequency of the image is increased, then the Fourier transform of the signal increases in the frequency domain (that is, the frequency (in Hz) of the signal increases); and vice versa.
It will be recalled that the image signal discussed above is a sampled signal. Nyquist's Rule concerning the sampling of signals states that, in order not to lose information contained in a signal, the signal must be sampled at a frequency (fs) that is equal to at least twice the bandwidth (fB) of the signal. Naturally, this criterion is complied with when the digital input signal is formed initially by sampling an analog signal. The frequency spectrum (Fourier transform) of the sampled signal in the frequency domain is shown by the solid lines in FIG. 1 of the accompanying drawings, which is a graph of amplitude v. frequency (Hz). The frequency spectrum comprises a baseband component 10 (up to fB). Also, the baseband is reflected symmetrically around the sampling frequency fs and its harmonics 2fs, 3fs etc. to produce higher frequency components 12. Provided that Nyquist's Rule is complied with (so that fs/2 is greater than fB) and provided that the signal is band-limited (low-pass filtered) so as to have a cut-off frequency of about fs/2, the higher frequency components 12 will be suppressed.
As explained above, when the sampled signal is subjected to compression in the spatial domain, its Fourier transform exhibits expansion in the frequency domain. Thus, the bandwidths of the components 10, 12 in FIG. 1 increase. As shown by dotted lines in FIG. 1, this can result in aliasing of the signal in that the bandwidth fB of the signal can exceed the Nyquist limit (fs/2) so that part of at least the lowest one of the higher frequency components 12 extends down into and is mixed with the baseband 10 so as to degrade the signal and therefore the image that it represents.
To prevent aliasing due to compression, a filter can be positioned in advance of the compression means to filter out those parts of the two-dimensional input spectrum that otherwise would exceed the Nyquist limit frequency (fs/2) once compression has been carried out. Ideally, the filter should have a flat pass band, infinite attenuation in the stop band and a transition band whose width approaches zero. Naturally, such an ideal filter cannot be realised in practice. However, by using a two-dimensional (2D) finite impulse response (FIR) filter, an adequate filter characteristic can be obtained.
As is known to those skilled in the art, a 2D-FIR filter is operative during successive clock periods equal to T(=1/fs) to effect filtration over a predetermined area of the 2D image or picture by processing a set of words or samples of the image signal having a predetermined spatial relationship to produce therefrom a filtered output word or sample. Specifically, during each clock period, the 2D-FIR filter is operative to calculate an output word or sample by multiplying a predetermined set of vertically and horizontally spaced words or samples of its input signal by respective weighting coefficients and summing the products of the multiplication operations. The necessary temporal delays to achieve the desired spatial relationship of the predetermined set of input words or samples can be achieved by delay elements positioned either in advance of or after respective multipliers used to carry out the multiplication operations. The delay elements thus can be considered to "tap" the image signal, in both directions. As is known to those skilled in the art, the response of the filter approaches more closely that of an ideal filter as the number of taps is increased.
Consider a compression means (for example a digital video effects unit) that is required to carry out compression over a range from zero compression (1:1) to, say, 100:1, the extent of compression being selectable in, for example, an infinitely variable manner. Consider also that the compression means is preceded by a 2D-FIR filter whose bandwidth is adjusted in accordance with the extent or degree of compression so as to avoid or at least minimize aliasing which otherwise would occur, in the event of compression, in the manner described above. In practice, it would not be feasible to design the filter so that its bandwidth is infinitely variable so that it can follow precisely the infinitely variable extent of compression. However, it would be feasible to design a 2D-FIR filter that would have a family of bandwidths (i.e. that would be capable of producing a family of responses) each corresponding to a respective range of compression. (In this connection, as is known in the art, the bandwidth of an FIR filter of a given configuration is determined by the values chosen for the weighting coefficients, whereby a family of responses can be obtained by previously calculating and storing a corresponding family of weighting coefficient sets). Thus, the filter might for example be designed to produce a family of bandwidths ranging from fs/2 (for zero compression) to fs/200 (for 100:1 compression). FIGS. 2A, 2B, 2C and 2D of the accompanying drawings show (in idealised form) responses that might be obtained for respective extents of compression of 1:1, 2:1, 3:1 and 100:1.
It should be appreciated that the image may be compressed in either or both of the horizontal and vertical directions, possibly by different respective degrees; and that a 2D-FIR filter has both horizontal and vertical bandwidths which may be varied independently of one another by suitably choosing the values of the weighting coefficients. Thus, it should be appreciated that the comments made above (and below) relating to bandwidth and compression apply independently to the horizontal and vertical directions, respectively.
In this connection, as is known to those skilled in the art, the bandwidth of a system for handling a two-dimensional (vertical/horizontal) sampled image signal can be represented in the spatial domain by a two-dimensional frequency response as represented in FIG. 3 of the accompanying drawings. In FIG. 3, the horizontal axis represents a scale of horizontal spatial frequency in the positive and negative senses (H+ and H-) in units of cycles per picture (image) width, the vertical axis represents a scale of vertical spatial frequency in the positive and negative senses (V+ and V-) in units of cycles per picture (image) height, the rectangle 14 represents the two-dimensional bandwidth of the system, and the dimensions 16 and 18 represent the vertical and horizontal bandwidths, respectively. If the system comprises a 2D-FIR filter the vertical and horizontal bandwidths can be controlled in a manner known per se by varying the values of the weighting coefficients.
As indicated above, for a 2D-FIR filter of a particular configuration the bandwidth can be varied by altering the values of the weighting coefficients. However, if the bandwidth is to be varied over a large range, for example over the range from fs/2 to fs/200 quoted above, and if the filter response is to be a reasonable approximation to the ideal response over the whole range, a very large number of taps is required. Accordingly, since, for each direction, the amount of hardware is approximately proportional to the number of taps, the disadvantage arises that the filter would be very large and expensive. An object of the present invention is to overcome or at least to reduce this disadvantage.